package com.adamjwh.sort;

import java.util.Arrays;

/**
 * 计数排序
 * 
 * @author adamjwh
 * 
 * 算法描述：
 * 找出待排序的数组中最大和最小的元素；
 * 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
 * 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
 * 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
 *
 */
public class CountingSort {

	public static void countingSort(int[] array) {
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		for (int i=0; i<array.length; i++) {
			if (array[i] < min) {
				min = array[i];
				continue;
			}
			if (array[i] > max) {
				max = array[i];
			}
		}
		
		int[] countArray = new int[max-min+1];
		for (int i=0; i<array.length; i++) {
			countArray[array[i]-min] ++;
		}
		
		int k = 0;
		for (int i=0; i<countArray.length; i++) {
			for (int j=0; j<countArray[i]; j++) {
				array[k++] = min + i;
			}
		}
	}
	
	//测试
	public static void main(String[] args) throws Exception {
	    int[] arr = {1,3,3,12,-7,8,8,4,65,-22, 8};

	    countingSort(arr);

	    System.out.println(Arrays.toString(arr));
	}
	
}
